﻿module StronglyConnectedComponents

    //http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm
    //For a different algorithm see
    //Reference: http://www.logarithmic.net/pfh-files/blog/01208083168/sort.py

    type Node<'a>(input: 'a) = 
        class
            let value = input
            let links = System.Collections.Generic.List<Node<'a>>()

            member this.Value with get() = value
            member this.Links with get() = links

            [<DefaultValue>]
            val mutable startTime: int; //for debugging
           
            [<DefaultValue>]
            val mutable finishTime: int; //used by strongly connected components
        
        end

    let newNode(value) = Node(value)
       //{value = value;links = System.Collections.Generic.List<_>();finishTime = 0;startTime = 0}

    type Graph<'a> = Graph of  (Node<'a> [])
        
    let toDict(input:seq<'k*'v>) = 
        let d = System.Collections.Generic.Dictionary<_,_>()
        for (k,v) in input do
            d.Add(k,v)
        d
            
    let transpose(Graph graph: Graph<'a>): Graph<'a> = 
        let newNodes = graph |> Seq.map(fun node -> 
                                                node,
                                                let n = newNode(node.Value)
                                                n.startTime <- node.startTime
                                                n.finishTime <- node.finishTime
                                                n)
                             |> toDict

        graph |> Seq.iter(fun node -> 
                                let newNode = newNodes.[node]
                                node.Links |> Seq.iter(fun linkedNode ->
                                                                let newLinkedNode = newNodes.[linkedNode]
                                                                newLinkedNode.Links.Add(newNode)))
        newNodes.Values |> Array.ofSeq |> Graph

    let setDFSVisitTimes(Graph graph: Graph<'a>): unit = 
        let notVisited = -1
        graph |> Array.iter(fun node -> node.finishTime <- notVisited)
        let rec visit (time: int) (node: Node<'a>)  = 
            if (node.finishTime = notVisited) then
                let mutable vartime = time + 1
                node.finishTime <- 0
                node.startTime <- vartime
                for child in node.Links do
                    //vartime <- vartime + 1
                    vartime <- visit vartime child
                vartime <- vartime + 1  
                node.finishTime <- vartime
                vartime
            else
                time
        graph |> Array.fold visit 0 |> ignore
    
    let getComponents(Graph graph: Graph<'a>): Node<'a>[][] = 
        let notVisited = -1
        graph |> Array.iter(fun node -> node.finishTime <- notVisited)
        let rec visit (node: Node<'a>) (visited: System.Collections.Generic.List<_>) = 
            if (node.finishTime = notVisited) then
                node.finishTime <- 0
                visited.Add(node)
                for child in node.Links do
                    visit child visited
        let nodeToComponentId = System.Collections.Generic.Dictionary<Node<'a>, int>()
        let componentId = ref 1        
        let findStartNode (nodes: seq<Node<'a>>) = 
            let toId(n: Node<'a>):int =
                if n.Links.Count = 0 then 0
                else 
                    n.Links |> Seq.map(fun l -> 
                            let ok, v = nodeToComponentId.TryGetValue l
                            if ok then v
                            else System.Int32.MaxValue) |> Seq.min
            nodes |> Seq.minBy(fun node -> toId node)
        [|
            for node in graph do
                if (node.finishTime = notVisited) then
                    let visited = System.Collections.Generic.List<_>()
                    visit node visited
//                    let startNode = findStartNode visited
//                    visited |> Seq.iter(fun node -> node.finishTime <- notVisited)
//                    visited.Clear()
//                    visit startNode visited //revisit
                    let sorted = visited |> Array.ofSeq |> Array.sortBy(fun n -> n.startTime)

                    componentId := !componentId + 1
                    yield sorted //(Array.ofSeq visited)
        |]
             
    
    let stronglyConnectedComponents(Graph graph: Graph<'a>):  (Node<'a>[] [] * Graph<'a>) =
        setDFSVisitTimes (Graph graph)
        //graph |> Seq.iter(fun node -> printfn "%A %d/%d" node.value node.startTime node.finishTime)
        let (Graph t) = transpose (Graph graph)
        Array.sortInPlaceBy(fun (node: Node<'a>) -> - node.finishTime) t
        let g = (Graph t)
        getComponents g, g